package com.zm.demo.core.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

import static java.lang.System.out;

/**
 * @author zoum
 * @create 2020/1/7 11:48
 */
public class LevelOrder {

    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root != null){
            result.add(Arrays.asList(root.val));
            TreeMap<Integer, List<Integer>> levelMap = new TreeMap<>(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o1.compareTo(o2);
                }
            });
            getLevelMap(levelMap, root.children, 1);
            if (levelMap.size() > 0){
                for (Map.Entry<Integer, List<Integer>> entry : levelMap.entrySet()){
                    result.add(entry.getValue());
                }
            }
        }
        return result;

    }

    public void getLevelMap(TreeMap<Integer, List<Integer>> levelMap, List<Node> children, int level){
        if (children == null || children.size() == 0){
            return;
        }
        int nextLevel = level + 1;
        for (int i = 0; i < children.size(); i++) {

            Node _this = children.get(i);
            if ((levelMap.get(level)) == null){
                List<Integer> list = new ArrayList<>();
                list.add(_this.val);
                levelMap.put(level, list);
            }else {
                levelMap.get(level).add(_this.val);
            }
            getLevelMap(levelMap, _this.children, nextLevel);
        }
    }

    public static void main(String[] args){

        List<Node> list3 = Arrays.asList(new Node(5, null), new Node(6, null));

        List<Node> list2 = Arrays.asList(new Node(3, list3), new Node(2, null), new Node(4, null));

        Node root = new Node(1, list2);


//        {"val":1,"children":[{"val":3, "children":[{"val":5, "children":null},{"val":5, "children":null}]},{"val":2, "children":null},{"val":4, "children":null}]}
        out.println(new LevelOrder().levelOrder(root));
    }
}

